Московский государственный университет имени М. В. Ломоносова

Факультет вычислительной математики и кибернетики Кафедра исследования операций

Отчет по преддипломной практике

�Оптимизация крупных закупок в модели Бертсимаса-Ло с учетом дополнительной информации�

Студентка 411 группы А. И. Макарова

Научный руководитель к.ф.-м.н., доцент В. В. Морозов

Москва, 2014

Содержание

2

Введение

В работе рассматривается рынок, движимый заявками, который представляется в виде книги лимитированных заявок– множество заявок на покупку и продажу, доступных в данный момент. Каждая заявка в книге содержит информацию о своей цене и соответствующем объеме. При сделке объема V происходит исполнение лучших(по цене) заявок суммарным объемом V, т.е данные заявки изымаются из книги. В любой момент игроки могут выставлять и снимать свои заявки по усмотрению.

Изучается динамика стратегии, которая обеспечивает минимизацию величины дисперсии затрат рынка, при условии ограниченных средних затрат. Крупная закупка на рынке некоторого актива приводит к увеличению его цены исполнения, поскольку из книги изымаются заявки с низкими ценами и число таких заявок ограничено. Для оптимизации таких покупок следует учитывать динамику изменения цены.

Модель Бертсимаса-Ло [1] предполагает наличие одного инвестора, который может совершать покупки достаточно большого размера, для которых необходимо учитывать влияние на цену. Так же отметим, что это дискретная модель с равномерным разбиением по времени и она не учитывает временное влияние на цену. Постоянное влияние в этой модели зависит от объема сделки.

Постановка задачи

В рассматриваемой модели инвестор стремится приобрести актив в большом количестве в течении фиксированного отрезка времени [0, T]. Как было сказано выше, отрезок разбивается на равные части Δt = \frac{T}{N}:

0 = t_{0} < t_{1} < … < t_{N} = T.

A — объем совершаемой покупки. Покупки совершаются в моменты времени t_{i}, i = 0, …, N. x = (x_{0}, x_{1}, …, x_{N}) — стратегия инвестора. x_{i} ⩾ 0 — объем покупки в момент времени t_{i}.

∑_{i=0}^{N} x_{i} = A

P_{i} — стоимость актива в момент времени t_{i}. P_{−1} — стоимость актива, сложившаяся на рынке до начала торгов Динамика цен подчиняется закону геометрического броуновского движения: P_{i} = P_{i−1} + αx_{i} + u_{i}, i = 1, …, N u_{i} — независимые одинаково распределенные случайные величины. 𝔼u_{i} = 0, V ar u_{i} = σ^{2}Δt; α > 0 — коэффициент влияния покупки на цену P_{0} = P_{−1} + αx_{0}, отсюда

P_{i} = P_{−1} + α ∑_{j=0}^{i} x_{j} + ∑_{j=1}^{i} u_{j}.

𝔼P_{i} = P_{−1} + α ∑_{j=0}^{i} x_{j},

V arP_{i} = iσ^{2}Δt. 𝔼 [∑_{i=0}^{N} P_{i}x_{i}] — средние затраты.

𝔼 [∑_{i=0}^{N} P_{i}x_{i}] = ∑_{i=0}^{N} x_{i} (P_{−1} + α ∑_{j=0}^{i} x_{j}) = ∑_{i=0}^{N} x_{i}P_{−1}+α ∑_{i=0}^{N} (∑_{j=0}^{i} x_{j}) x_{i} = AP_{−1}+α ∑_{i=0}^{N} (∑_{j=0}^{i} x_{j}) x_{i}

𝔼 [∑_{i=0}^{N} P_{i}x_{i}] → min ⟺ ∑_{i=0}^{N} (∑_{j=0}^{i} x_{j}) x_{i} → min

Минимизация средних затрат

Рассмотрим задачу минимизации средних затрат в данной модели:

\begin{cases}f(x) = ∑_{i=0}^{N} (∑_{j=0}^{i} x_{j}) x_{i} → min, \\ ∑_{i=0}^{N} x_{i} = A, x_{i} ⩾ 0. \end{cases}

Известно, что оптимальной стратегией является:

x_{0} = x_{1} = … x_{N} = \frac{A}{N + 1}.

Т.е. Затраты минимальны при равномерных закупках.

Минимизация дисперсии затрат с ограничением на максимальное значение средних затрат

Введем новые обозначения:

∑_{i=j}^{N} x_{j} = X_{j} — сколько осталось купить в момент времени j, X_{0} = A, В новых обозначениях:

c(x) = 𝔼 [∑_{i=0}^{N} P_{i}x_{i}] = ∑_{i=0}^{N} x_{i} (P_{−1} + α ∑_{j=0}^{i} x_{j}) = AP_{−1} + α ∑_{i=0}^{N} X_{i}(X_{i} − X_{i+1}).

V ar [∑_{i=0}^{N} P_{i}x_{i}] = σ^{2}Δt ∑_{i=1}^{N} X_{i}^{2}.

V ar [∑_{i=0}^{N} P_{i}x_{i}] → min ⟺ ∑_{i=1}^{N} X_{i}^{2} → min.

Сформулируем задачу:

\begin{cases}∑_{i=1}^{N} X_{i}^{2} → min, \\ 𝔼 [∑_{i=0}^{N} P_{i}x_{i}] = AP_{−1} + α ∑_{i=0}^{N} X_{i}(X_{i} − X_{i+1}) ⩽ C_{0}, \\ A = X_{0} ⩾ X_{1} ⩾ … ⩾ X_{N} ⩾ X_{N+1} = 0. \end{cases}

Решение задачи

Целевая функция является квадратичной, как и ограничение. Для решения используется метод множетелей Лагранжа.

Выпишем функцию Лагранжа

L(X̃, λ_{0}, λ_{1}) = λ_{0} ∑_{i=1}^{N} X_{i}^{2} + λ_{1} (AP_{−1} + α ∑_{i=0}^{N} X_{i}(X_{i} − X_{i+1}) − C_{0}) .

X̃ = (X_{0}, X_{1}, …, X_{N}) λ_{0}, λ_{1} ⩾ 0 и одновременно не равны нулю.

В общем случае задача нерегулярная, поэтому рассмотрим два случая: Первый — λ_{0} = 0, тогда λ_{1} > 0, второй — λ_{0} ≠ 0.

Рассмотрим первый случай: Необходимое условие минимума:

LX̃^{′} = αλ_{1}(−X_{i−1} + 2X_{i} − X_{i+1}) = 0, i = 1, …, N.

Из условия дополняющей нежесткости:

AP_{−1} + α ∑_{i=0}^{N} X_{i}(X_{i} − X_{i+1}) − C_{0} = 0,

и должно выполняться:

X_{i} − X_{i+1} ⩾ 0, i = 1, …, N.

Решаем разностное уравнение

\begin{cases}−X_{i−1} + 2X_{i} − X_{i+1} = 0, \\ X_{0} = A, \\ X_{N+1} = 0. \end{cases}

Ищем решение в виде: X_{t} = ξ^{t}. Характериситическое уравнение:

ξ^{2} − 2ξ + 1 = 0
(ξ − 1)^{2} = 0

ξ = 1 — корень кратности 2.

X_{t} = ξ^{t}(C_{1} + C_{2}t).

X_{0} = C_{1} = A, X_{N+1} = (C_{1} + C_{2}(N + 1)) = 0, A + C_{2}(N + 1) = 0 ⇒ C_{2} = −\frac{A}{N+1}. Таким образом, решение для X_{t} имеет вид:

X_{t} = A − \frac{A}{N + 1}t.

Проверим условие X_{i} − X_{i+1} ⩾ 0:

X_{i} − X_{i+1} = A − \frac{A}{N + 1}i − A + \frac{A}{N + 1}(i + 1) = \frac{A}{N + 1} ⩾ 0.

Рассмотрим второй случай, когда λ_{0} ≠ 0: Тогда: λ = \frac{λ_{1}}{λ_{0}} ⩾ 0.

Построим функцию Лагранжа:

L(X̃, λ) = ∑_{i=1}^{N} X_{i}^{2} + λ(AP_{−1} + α ∑_{i=0}^{N} X_{i}(X_{i} − X_{i+1})).

Выпишем производную и приравняем ее к нулю:

LX̃^{′} = 0 :

\begin{cases}2X_{1} + λα(−X_{0} + 2X_{1} − X_{2}) = 0, \\ 2X_{2} + λα(−X_{1} + 2X_{2} − X_{3}) = 0, \\ … \\ 2X_{N} + λα(−X_{N−1} + 2X_{N} − X_{N+1}) = 0. \end{cases}

Решаем разностное уравнение:

\begin{cases}2(1 + λα)X_{i} = λα(X_{i−1} + X_{i+1}), i = 1, …, N, \\ X_{0} = A, \\ X_{N+1} = 0. \end{cases}

Так как λ > 0, α > 0, то можно сделать замену:

ω = \frac{1}{λα} + 1, ω > 1.

Тогда решаемые уравнения преобразуются к виду:

αωX_{i} = X_{i−1} + X_{i+1}.

Будем, как и в предыдущем случае, искать решение в виде X_{t} = ξ^{t}: Характеристическое уравнеие:

ξ^{2} − 2ωξ + 1 = 0,
ξ_{1,2} = ω ± \sqrt{ω^{2} − 1}.
ξ_{1}ξ_{2} = 1, ξ_{1} > 1, 0 < ξ_{2} < 1.

Решение имеет вид:

X_{t} = C_{1}ξ_{1}^{t} + C_{2}ξ_{2}^{t} = C_{1}ξ_{2}^{−t} + C_{2}ξ_{2}^{t}.

Из начальный условий найдем C_{1} и C_{2}:

X_{0} = C_{1} + C_{2} = A,

X_{N+1} = C_{1}ξ_{2}^{−(N+1)} + C_{2}ξ_{2}^{N+1} = 0.

Таким образом, решение имеет вид:

X_{t} = A (\frac{−ξ_{2}^{2(N+1)}ξ_{2}^{−t} + ξ_{2}^{t}}{1 − ξ_{2}^{2(N+1)}} ) .

Легко проверяется, что X_{i} − X_{i+1} ⩾ 0.

Численные примеры и результаты работы прораммы

Рассмотрим задачу оптимизации с начальными данными: A = 10000; P_{−1} = 2; α = 0.001; C_{0} = 90000; N = 9;

Эта задача соответствует случаю, когда достигается ограничение равенства. λ = 2625

Рассмотрим другую задачу оптимизации с начальными данными: A = 10000; P_{−1} = 2; α = 0.00001; C_{0} = 90000; N = 9;

Эта задача соответствует случаю, когда равенство нигде не достигается. Причем C_{0} сильно больше средних затрат.

Если C_{0} всегда меньше затрат, решения оптимизационной задачи не существует.

Список литературы

[1] Bertsimas D., Lo А. W. Optimal control of execution costs. — Journal of Financial Markets— �1—1998—pp. 1-50.

[2] Андреев Н. А. Современные математические модели влияния на цену: приложение к задаче оптимальноо управления портфелем на рынке, движимом заявками.

— Сборник статей молодых ученых факультета ВМК МГУ. Выпуск 9. 2012

[3] Морозов В. В., Толли Н. И. Минимизация риска при крупных закупках на финансовом рынке. — International Journal of Open Information Technologies ISSN: 2307-8162 vol.2, no. 8, 2014

[4] Феллер В. Введение в теорию вероятностей и её приложения. В 2-х томах. Т.1. — М.: Мир, 1984.